package my.sort;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 桶排序
 *
 * @author AJun
 * @date 2020/11/1
 */
public class BucketSort extends Sort<Integer> {

    @SuppressWarnings("unchecked")
    @Override
    protected void sort() {
        List<Integer>[] buckets = new List[array.length];
        for (Integer i : array) {
            int bucketIndex = i / array.length;
            List<Integer> bucket = buckets[bucketIndex];
            if (bucket == null) {
                bucket = new LinkedList<>();
                buckets[bucketIndex] = bucket;
            }
            bucket.add(i);
        }

        // 对每个桶进行排序
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (bucket == null) {
                continue;
            }
            Collections.sort(bucket);
            for (Integer i : bucket) {
                array[index++] = i;
            }
        }
    }

}
